import java.util.PriorityQueue;

/**
 * @author hewei
 * @version 1.0
 * @description: 1029. 两地调度
 * @date 2022/10/18 20:11
 */

public class TwoCitySchedCost {

    public int twoCitySchedCost(int[][] costs) {
        PriorityQueue<Integer> heap1 = new PriorityQueue<>();
        PriorityQueue<Integer> heap2 = new PriorityQueue<>();
        int ans = 0;
        for (int[] cost : costs) {
            if (cost[0] >= cost[1]) {
                heap2.add(cost[0] - cost[1]);
                ans += cost[1];
            } else {
                heap1.add(cost[1] - cost[0]);
                ans += cost[0];
            }
        }
        int delta = Math.abs(heap1.size() - heap2.size());
        for (int i = 0; i < delta / 2; i++) {
            ans += (heap1.size() > heap2.size() ? heap1 : heap2).poll();
        }
        return ans;
    }
}
